//两个节点的最近公共祖先
//第一种方法：分成是三种情况，一：同侧，返回先找到的哪一个，
// 二：不同侧，返回根节点。三：看这两个节点是根节点不。
class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
  }
    public TreeNode lowestCommonAncestor(TreeNode root,
                           TreeNode p, TreeNode q) {
        if(root==null||p==null||q==null) {
            return null;
        }
            if(p==root||q==root){
            return  root;
        }
        TreeNode leftFlag=lowestCommonAncestor(root.left,q,p);
        TreeNode rightFlag=lowestCommonAncestor(root.right,q,p);
        if(leftFlag!=null&&rightFlag!=null){
            return root;
        }
         if(rightFlag!=null) {
             return rightFlag;
         }
        if(leftFlag!=null){
             return leftFlag;
        }
         return  null;
    }
}